package 算法基础模板.chapter_01;

import java.util.Scanner;

/**
 * 给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
 * <p>
 * 对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
 * <p>
 * 如果数组中不存在该元素，则返回“-1 -1”。
 * <p>
 * 输入格式
 * 第一行包含整数n和q，表示数组长度和询问个数。
 * <p>
 * 第二行包含n个整数（均在1~10000范围内），表示完整数组。
 * <p>
 * 接下来q行，每行包含一个整数k，表示一个询问元素。
 * <p>
 * 输出格式
 * 共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
 * <p>
 * 如果数组中不存在该元素，则返回“-1 -1”。
 * <p>
 * <p>
 * 整数二分  https://www.acwing.com/problem/content/791/ 数的范围
 *
 * @author Summerday
 */
public class BinarySearchTemplate {

    static int n, q;
    static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();

        nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        while (q-- > 0) {
            int k = sc.nextInt();
            int[] res = binarySearch(nums, k);
            for (int num : res) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    static int[] binarySearch(int[] nums, int k) {
        int l = 0, r = nums.length - 1;
        // 找到第一个 大于等于k 的数
        while (l < r) {
            int mid = l + r >>> 1;
            if (nums[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != k) return new int[]{-1, -1};
        int begin = l;
        l = 0;
        r = nums.length - 1;
        // 找到最后一个小于等于k 的数
        while(l < r){
            int mid = l + r + 1 >>> 1; // l = mid
            if(nums[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return new int[]{begin, l};
    }
}
